// 提交链接：https://leetcode.cn/problems/design-skiplist/
// lc1206. 设计跳表
// 完成日期：2024/10/18
// c++ 链表 数据结构

// 定义跳表中的节点结构
struct Node {
    int val; // 节点存储的值
    vector<Node*> next; // 指向不同层级下一个节点的指针

    // 节点构造函数
    Node(int v, int level)
        : val(v) // 初始化值
        , next(level, nullptr) {} // 初始化next指针为nullptr，大小为level
};

// 定义跳表类
class Skiplist {
public:
    const int p = RAND_MAX / 4; // 用于随机生成节点层数的概率因子
    const int maxLevel = 32; // 跳表的最大层数
    Node* head; // 指向跳表头节点（虚拟头节点）
    int level; // 当前跳表的最大层数

    // 跳表构造函数
    Skiplist() {
        head = new Node(-1, maxLevel); // 创建一个虚拟头节点
        level = 0; // 初始化当前层数为0
    }

    // 查找跳表中的目标值
    bool search(int target) {
        Node* curr = head; // 从头节点开始
        for (int i = level - 1; ~i; --i) { // 从最高层遍历到第0层
            curr = findClosest(curr, i, target); // 查找小于或等于目标值的最近节点
            if (curr->next[i] && curr->next[i]->val == target) return true; // 找到目标值
        }
        return false; // 未找到目标值
    }

    // 向跳表中添加一个数字
    void add(int num) {
        Node* curr = head; // 从头节点开始
        int lv = randomLevel(); // 随机生成新节点的层数
        Node* node = new Node(num, lv); // 创建一个新节点
        level = max(level, lv); // 更新当前最大层数
        for (int i = level - 1; ~i; --i) { // 遍历从最高层到第0层
            curr = findClosest(curr, i, num); // 查找当前层中小于目标值的最近节点
            if (i < lv) { // 如果当前层小于新节点的层数
                node->next[i] = curr->next[i]; // 将新节点的下一个指针指向当前节点的下一个节点
                curr->next[i] = node; // 将当前节点的下一个指针指向新节点
            }
        }
    }

    // 从跳表中删除一个数字
    bool erase(int num) {
        Node* curr = head; // 从头节点开始
        bool ok = false; // 标记数字是否找到并删除
        for (int i = level - 1; ~i; --i) { // 遍历从最高层到第0层
            curr = findClosest(curr, i, num); // 查找当前层中小于目标值的最近节点
            // 检查下一个节点是否为要删除的数字
            if (curr->next[i] && curr->next[i]->val == num) {
                curr->next[i] = curr->next[i]->next[i]; // 跳过要删除的节点
                ok = true; // 找到并删除数字
            }
        }
        // 更新最大层数
        while (level > 1 && !head->next[level - 1]) --level; // 如果最高层为空，则降低层数
        return ok; // 返回数字是否成功删除
    }

    // 查找小于或等于目标值的最近节点
    Node* findClosest(Node* curr, int level, int target) {
        while (curr->next[level] && curr->next[level]->val < target) 
            curr = curr->next[level]; // 移动到下一个节点，直到找到目标值或超出范围
        return curr; // 返回最近节点
    }

    // 随机生成新节点的层数
    int randomLevel() {
        int lv = 1; // 从1开始
        while (lv < maxLevel && rand() < p) // 随机生成层数
            ++lv; // 层数增加
        return lv; // 返回生成的层数
    }
};


/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */